﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection.Emit;

namespace Sigil.Impl
{
	internal class ReturnTracerResult
	{
		private class LabelEnumerableComparer : IEqualityComparer<IEnumerable<Label>>
		{
			public static readonly LabelEnumerableComparer Singleton = new LabelEnumerableComparer();

			private LabelEnumerableComparer()
			{
			}

			public Boolean Equals(IEnumerable<Label> x, IEnumerable<Label> y)
			{
				if (x == y) return true;
				if (x == null || y == null) return false;

				if (x.Count() != y.Count()) return false;

				using (var eX = x.GetEnumerator())
				using (var eY = y.GetEnumerator())
				{
					while (eX.MoveNext() && eY.MoveNext())
					{
						if (eX.Current != eY.Current) return false;
					}
				}

				return true;
			}

			public Int32 GetHashCode(IEnumerable<Label> obj)
			{
				if (obj == null) return 0;

				var ret = 0;

				foreach (var label in obj)
				{
					ret ^= label.GetHashCode();
				}

				return ret;
			}
		}

		public Boolean IsSuccess { get; private set; }

		public IEnumerable<IEnumerable<Label>> FailingPaths { get; private set; }

		private ReturnTracerResult()
		{
		}

		public static ReturnTracerResult Success()
		{
			return
					new ReturnTracerResult
					{
						IsSuccess = true
					};
		}

		public static ReturnTracerResult Failure(List<Label> path)
		{
			return
					new ReturnTracerResult
					{
						IsSuccess = false,

						FailingPaths = new IEnumerable<Label>[] { path.ToList() }
					};
		}

		public static ReturnTracerResult Combo(params ReturnTracerResult[] other)
		{
			var asArr = other;

			if (asArr.All(r => r.IsSuccess)) return Success();

			var allPaths = asArr.Where(r => !r.IsSuccess).SelectMany(r => r.FailingPaths).ToList();

			var uniqePaths = allPaths.Distinct(LabelEnumerableComparer.Singleton).ToList();

			return
					new ReturnTracerResult
					{
						IsSuccess = false,

						FailingPaths = uniqePaths
					};
		}
	}

	internal class ReturnTracer
	{
		private List<Tuple<OpCode, Label, Int32>> Branches;
		private Dictionary<Label, Int32> Marks;
		private List<Int32> Returns;
		private List<Int32> Throws;

		public ReturnTracer(List<Tuple<OpCode, Label, Int32>> branches, Dictionary<Label, Int32> marks, List<Int32> returns, List<Int32> throws)
		{
			Branches = branches;
			Marks = marks;
			Returns = returns;
			Throws = throws;
		}

		private static Boolean IsUnconditionalBranch(OpCode op)
		{
			return
					op == OpCodes.Br ||
					op == OpCodes.Br_S ||
					op == OpCodes.Leave ||
					op == OpCodes.Leave_S;
		}

		private Dictionary<Int32, ReturnTracerResult> Cache = new Dictionary<Int32, ReturnTracerResult>();

		private ReturnTracerResult TraceFrom(Int32 startAt, List<Label> path, HashSet<Label> pathLookup)
		{
			ReturnTracerResult cached;
			if (Cache.TryGetValue(startAt, out cached))
			{
				return cached;
			}

			var nextBranches = Branches.Where(b => b.Item3 >= startAt).GroupBy(g => g.Item3).OrderBy(x => x.Key).FirstOrDefault();
			var orReturns = Returns.Where(ix => ix >= startAt && (nextBranches != null ? ix < nextBranches.Key : true));
			var orThrows = Throws.Where(ix => ix >= startAt && (nextBranches != null ? ix < nextBranches.Key : true));

			if (orReturns.Any())
			{
				Cache[startAt] = cached = ReturnTracerResult.Success();
				return cached;
			}

			if (orThrows.Any())
			{
				Cache[startAt] = cached = ReturnTracerResult.Success();
				return cached;
			}

			if (nextBranches == null)
			{
				Cache[startAt] = cached = ReturnTracerResult.Failure(path);
				return cached;
			}

			var ret = new List<ReturnTracerResult>();

			foreach (var nextBranch in nextBranches)
			{
				if (pathLookup.Contains(nextBranch.Item2))
				{
					Cache[startAt] = cached = ReturnTracerResult.Success();
					ret.Add(cached);
					continue;
				}

				var branchOp = nextBranch.Item1;

				var branchTo = Marks[nextBranch.Item2];

				var removeFromPathAt = path.Count;
				path.Add(nextBranch.Item2);
				pathLookup.Add(nextBranch.Item2);

				var fromFollowingBranch = TraceFrom(branchTo, path, pathLookup);

				path.RemoveAt(removeFromPathAt);
				pathLookup.Remove(nextBranch.Item2);

				if (IsUnconditionalBranch(branchOp))
				{
					Cache[startAt] = cached = fromFollowingBranch;
					//return cached;
					ret.Add(cached);
					continue;
				}

				var fromFallingThrough = TraceFrom(startAt + 1, path, pathLookup);

				Cache[startAt] = cached = ReturnTracerResult.Combo(fromFallingThrough, fromFollowingBranch);

				ret.Add(cached);
			}

			Cache[startAt] = cached = ReturnTracerResult.Combo(ret.ToArray());
			return cached;
		}

		public ReturnTracerResult Verify()
		{
			var firstLabel = Marks.OrderBy(o => o.Value).First().Key;
			var firstIx = Marks[firstLabel];

			var path = new List<Label>();
			path.Add(firstLabel);
			var pathLookup = new HashSet<Label>(path);

			return TraceFrom(firstIx, path, pathLookup);
		}
	}
}